package com.data_structure_algorithm.data_structure.stack;

/**
 * @author 何章怀晓 hezhanghuaixiao
 * @version V1.0
 * @desc 链表实现栈
 */
public class StackLinkedList {

  int max;//链表长度最大值

  StackNode top;//栈顶元素,即链表尾端

  StackNode head;//代表链表首节点，即栈底

  StackNode stack;

  int num; //栈内元素个数

  public StackLinkedList(int max) {
    this.max = max;
    stack = new StackNode(-1);//初始化链表
  }

  public void add(StackNode node) {

    if (isStackMax()) {
      System.out.println("栈满");
      return;
    }
    StackNode temp = head;
    //确定栈底

    if (temp == null) {
      head = node;
      top = node;
      stack = node;
      num++;
      return;
    }

    while (true) {
      if (temp.next == null) {
        break;
      }
      temp = temp.next;
    }

    temp.next = node;

    //维护top,当前加入的节点即top节点
    top = node;
    num++;


  }


  public StackNode pop() {
    StackNode stackNode = stack;
    if (stackNode == null) {
      return null;
    }
    //栈顶元素
    StackNode top = this.top;

    StackNode temp = head;

    if (head == top) {
      return head;
    }
    //取出栈顶即链表尾部的数据
    while (true) {

      this.top = temp;//top的位置不断变化,先确定top位置

      if (temp.next == top) {//如果下一个是栈顶（链表尾）
        break;
      }
      temp = temp.next;//后移


    }

    return temp.next;


  }


  public void showStack() {
    StackNode stackNode = stack;
    if (stackNode == null) {
      return;
    }

    for (int i = 0; i < max; i++) {
      StackNode pop = pop();
      System.out.println("--------------" + pop.id);
    }
  }


  public boolean isStackMax() {

    if (stack == null) {
      System.out.println("栈空");
    }
    return max == num;
  }


  public static void main(String[] args) {
    StackLinkedList stackLinkedList = new StackLinkedList(5);
    stackLinkedList.add(new StackNode(0));
    stackLinkedList.add(new StackNode(1));
    stackLinkedList.add(new StackNode(2));
    stackLinkedList.add(new StackNode(3));
    stackLinkedList.add(new StackNode(4));
    //stackLinkedList.add(new StackNode(4));

    stackLinkedList.showStack();
  }
}


class StackNode {

  int id;

  StackNode next;

  public StackNode(int id) {
    this.id = id;
  }
}
